1. Field of the Invention
The present invention relates to a method for tracing an optimal quantization path using a Trellis-based adaptive quantizer, and in particular to an improved method for tracing an optimal path using a Trellis-based adaptive quantizer which can accelerate quantization path tracing and simplify computation thereof, by excluding the quantization path tracing after an turning point of distortion and after an optimal quantization level to non-zero at a branch directed to the non-zero node from a zero node.
2. Description of the Background Art
In general, a Trellis-based adaptive quantizer codes coefficients to which image blocks are transformed by transformation methods, such as a discrete cosine transformation (DCT) in a Trellis structure, into a run-length code and entropy constrained code.
FIG. 1 is a concept diagram of data quantization using the Trellis-based adaptive quantizer in the conventional art. Whenever predetermined coefficients C1, C2, . . . , Ci, . . . , C64 from a predetermined node at an initial state are quantized one by one, corresponding stages S1, S2, . . . , S64 are formed. Here, white circles imply code as xe2x80x980xe2x80x99, Ri denotes a run length (which means the number of code as xe2x80x980xe2x80x99), and black circles imply code of the coefficients Ci to a level (or amplitude) Li.
In the above example, when it is presumed that one image block is divided into 8xc3x978, the number of the coded coefficients is 64 thereby. A solid line indicates a branch for coding the coefficient as non-zero from a predetermined node, and a dotted line indicates a branch for coding the coefficient as zero from a predetermined node.
At this time, the respective stages are defined as an algorithm of performing Huffman coding on a predetermined symbol, a run length and a level. Accordingly, paths between the branches connecting the nodes of the respective stages are defined as a metric. The metric J is represented by the following expression.
J=D+xcexxc2x7R
Here, R denotes the number of bits used for coding the coefficient (for example, R=64), D denotes distortion between the coefficients of each stage and the coded coefficient (or the absolute value of the subtraction between the coefficients of each stage and the coded coefficient), and xcex denotes Lagrange constant.
When the data is quantized by the expression J(n)=D(n)+xcexxc2x7R(n) in order to obtain a minimum metric J(n) to the n-th stage S(n), the conventional method for tracing the optimal quantization path using the Trellis-based adaptive quantizer adapts only the distortion D, not R(n), computes the metrics for all the paths, selects the metric at the optimal state, and determines the optimal path.
However, the conventional method has a disadvantage in that the optimal path is determined by computing all the metrics in regard to the whole paths or branches. As a result, a system adapted the conventional method codes the data lately and complicatedly, and thereby takes a long time to compute the optimal path tracing.
Accordingly, it is a primary object of the present invention to provide an improved method for tracing an optimal path using a Trellis-based adaptive quantizer, which can search a quantization interval at a high speed by excluding branches which do not require path tracing in a Trellis structure.
It is another object of the present invention to provide an improved method for tracing an optimal quantization path using a Trellis-based adaptive quantizer which can accelerate quantization path tracing and simplify computation thereof, by excluding the quantization path tracing after a turning point of distortion in the Trellis-based adaptive quantizer and after an optimal quantization level to non-zero at a branch directed to a non-zero node from a zero node.
In order to achieve the above-described objects of the present invention, in a Trellis-based adaptive quantizer codes coefficients to which image blocks are transformed by transformation methods in a Trellis structure into a run-length code and entropy constrained code, a method for tracing an optimal path using the Trellis-based adaptive quantizer comprises, a step for excluding quantization path tracing of branches after a turning point of distortion, on the basis of arrangement of a quantization interval and monotonic increasing characteristics of a code word length, in a Trellis structure of generating one stage whenever the coefficients are quantized one by one from a node, and a step for excluding path tracing after an optimal coding level to non-zero at the branches positioned from zero node to non-zero node, based on independence of the respective stages, when quantizing coefficients to non-zero node from the node.